/**
 * 
 */
package dp;

import java.util.LinkedList;
import java.util.List;

import utils.PrintUtils;

/**
 * @author Michael
 * 
 *         Given a sequence of n real numbers A(1) ... A(n), determine a
 *         subsequence (not necessarily contiguous) of maximum length in which
 *         the values in the subsequence form a strictly increasing sequence.
 */
public class LongestIncreaseSubSequence {

	/*
	 max = 0
			 for i = 1, 2, ... n:
			    binary search for the largest positive j ≤ mx
			      such that arr[lengths[j]] < arr[i] (or set j = 0 if no such value exists)
			    backtrack[i] = lengths[j]
			    if j == max or arr[i] < arr[lengths[j+1]]:
			       lengths[j+1] = i
			       max = max(max, j+1)
	*/

	// time nlogn, space n
	public List<Integer> lis(int[] arr) {
		int[] lengths = new int[arr.length + 1];
		lengths[0] = -1;
		int[] backtrack = new int[arr.length];
		int max = 0;
		for (int i = 0, size = arr.length; i < size; i++) {
			int j = binarySearchI(arr, lengths, i, 1, max);
			j = j == -1 ? 0 : j;
			backtrack[i] = lengths[j];
			if (j == max || arr[i] < arr[lengths[j + 1]]) {
				lengths[j + 1] = i;
				max = max < j + 1 ? j + 1 : max;
			}
		}

		List<Integer> list = new LinkedList<Integer>();
		int i = lengths[max];
		while (i != -1) {
			list.add(0, arr[i]);
			i = backtrack[i];
		}

		return list;
	}

	private int binarySearchI(int[] arr, int[] lengths, int target, int left,
			int right) {
		int position = -1;
		while (left <= right) {
			int mid = left + (right - left);
			if (arr[lengths[mid]] >= arr[target]) {
				right = right - 1;
			} else {
				position = mid;
				left = mid + 1;
			}
		}

		return position;
	}

	private int binarySearchR(int[] arr, int[] lengths, int target, int left,
			int right) {

		if (left == right) {
			if (arr[lengths[left]] < arr[target])
				return left;
			else
				return -1;
		}

		if (left > right)
			return -1;

		if (right - left == 1) {
			if (arr[lengths[right]] < arr[target])
				return right;
			if (arr[lengths[left]] < arr[target])
				return left;
			else
				return -1;
		}

		int mid = left + (right - left) / 2;
		if (arr[lengths[mid]] >= arr[target]) {
			return binarySearchR(arr, lengths, target, left, mid - 1);
		} else {
			return binarySearchR(arr, lengths, target, mid, right);
		}
	}

	// s[i]: length of longest increasing sequence ending at a[i]
	// s[i] = max(s[j]) + 1 for all j<i and a[j]<a[i]
	// answer: max(s[i]) for all i
	// complexity: O(n^2), O(n)
	public static int getLISSDP(int[] arr, List<Integer> sequence) {
		assert (arr != null);
		assert (arr.length >= 0);

		int maxIndex = 0;
		int[] lengths = new int[arr.length];
		lengths[0] = 1;
		// Map<Integer, Integer> backtrack = new HashMap<Integer, Integer>();
		int[] backtrack = new int[arr.length];
		// backtrack.put(0, -1);
		backtrack[0] = -1;
		for (int i = 1; i < arr.length; ++i) {
			int maxI = -1, maxLength = 0;
			for (int j = i - 1; j >= 0; --j) {
				if (arr[j] < arr[i] && lengths[j] > maxLength) {
					maxI = j;
					maxLength = lengths[j];
				}
			}
			lengths[i] = maxI == -1 ? 1 : lengths[maxI] + 1;
			// backtrack.put(i, maxI);
			backtrack[i] = maxI;
			maxIndex = lengths[i] > lengths[maxIndex] ? i : maxIndex;
		}

		int i = maxIndex;
		while (i != -1) {
			sequence.add(0, arr[i]);
			// i = backtrack.get(i);
			i = backtrack[i];
		}
		return lengths[maxIndex];
	}

	/*
	 * // nlogn const int MAXN = 10010;
	 * 
	 * class LIS { public: int data[MAXN], L[MAXN];
	 * 
	 * int n, tmpar[MAXN], from[MAXN];
	 * 
	 * inline bool cmp(int a, int b) { return a > b; }
	 * 
	 * int calc() { int ret = 0; for (int i = 0; i < n; i++) { // binary search
	 * int head = 1, tail = ret, mid; while (head <= tail) { mid = (head + tail)
	 * >> 1; if (cmp(data[tmpar[mid]], data[i])) head = mid + 1; else tail = mid
	 * - 1; } tmpar[head] = i; from[i] = tmpar[head - 1]; if (head > ret) ret++;
	 * } int tmp = tmpar[ret]; for (int i = ret; i > 0; i--) { L[i - 1] =
	 * data[tmp]; tmp = from[tmp]; } return ret; } };
	 * 
	 * L return seq, calc() return length
	 */
	public int getLISS_DP(int[] arr) {
		assert (arr != null);
		assert (arr.length > 0);

		int result = 0;
		int[] longestSoFar = new int[arr.length];
		int[] previous = new int[arr.length];
		longestSoFar[0] = 1;
		previous[0] = -1;

		for (int i = 1, size = arr.length; i < size; ++i) {
			int longest = 0;
			for (int j = i - 1; j >= 0; --j) {
				if (arr[j] < arr[i] && longestSoFar[j] > longest) {
					longest = longestSoFar[j];
					previous[i] = j;
				}
			}
			longestSoFar[i] = longest + 1;
		}

		int lastPosition = 0;
		for (int i = 0; i < longestSoFar.length; ++i) {
			// result = longestSoFar[i] > result ? longestSoFar[i] : result;
			if (result < longestSoFar[i]) {
				lastPosition = i;
				result = longestSoFar[i];
			}
		}

		do {
			System.out.printf("%d, ", arr[lastPosition]);
			lastPosition = previous[lastPosition];
		} while (lastPosition > -1);
		System.out.println();

		return result;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// System.out.printf("Longest Increasing Subsequence\n");
		// LongestIncreaseSubSequence liss = new LongestIncreaseSubSequence();
		int[] arr = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
		//int[] arr = { 1, 2, 4, 3 };
		// Queue<Double> s = new LinkedList<Double>();
		// System.out.printf("# of longest increasing subsequence is %d\n",
		// LongestIncreaseSubSequence.getLISSDP(arr));
		// double[] arr = CreateUtils.randRealArray(10, 10);
		PrintUtils.printArray(arr);
		List<Integer> sequence = new LinkedList<Integer>();
		System.out.println(getLISSDP(arr, sequence));
		PrintUtils.printList(sequence);

		LongestIncreaseSubSequence liss = new LongestIncreaseSubSequence();
		List<Integer> sequence1 = liss.lis(arr);
		PrintUtils.printList(sequence1);
	}

	/**
	 * 
	 */
	public LongestIncreaseSubSequence() {
		// TODO Auto-generated constructor stub
	}
}
